package algorithm.sort;

import java.util.Arrays;

public class QuickSort {

  public static void main(String[] args) {

//    for (int j = 0; j < 10; j++) {
//
//
//      int i1 = 4;
//      int[] arr = new int[i1];
//      for (int i = 0; i < i1; i++) {
//        arr[i] = new Random().nextInt(100);
//      }
//
//      System.out.println(Arrays.toString(arr));
//      sort(arr, 0, arr.length - 1);
//      System.out.println(Arrays.toString(arr));
//
//
//      System.out.println();
//
//    }

    int[] arr = new int[3];
    arr[0] = 2;
    arr[1] = 3;
    arr[2] = 2;

    System.out.println(Arrays.toString(arr));
    sort(arr, 0, arr.length - 1);
    System.out.println(Arrays.toString(arr));

  }


  //快速排序
  public void sort(int[] arr) {
//
//    int mid = sort(arr, 0, arr.length - 1);
//

  }

  public static int sort(int[] arr, int low, int high) {

    if (low >= high) {
      return 0;
    }
    //地位指针
    int l = low;
    //高位指针
    int h = high;
    int base = arr[low];
    l++;
    while (true) {
      //i < k 同时防止下标越界
      while (arr[l] < base && l < high) {
        l++;
      }
      while (base <= arr[h] && low < h) {
        h--;
      }
      if (l >= h) break;
      //互换
      exchange(arr, l, h);
    }

    exchange(arr, low, h);

    return h;
  }

  public static void exchange(int[] arr, int a, int b) {
    int tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
  }

}
